package 中等.其他;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 给你一个 m x n 的二元矩阵 matrix ，且所有值被初始化为 0 。请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j) ，并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。
 * <p>
 * 尽量最少调用内置的随机函数，并且优化时间和空间复杂度。
 * <p>
 * 实现 Solution 类：
 * <p>
 * Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
 * int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1
 * void reset() 将矩阵中所有的值重置为 0
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/random-flip-matrix
 */
public class 随机翻转矩阵_519 {

    /**
     * 最多调用 1000 次 flip 和 reset 方法。
     * 用来存储所有随机位置，和被交换位置，最多有2000个元素
     * key-第几个位置，value-默认=key，每次两个entry的value进行交换
     */
    private Map<Integer, Integer> map = new HashMap<>();

    /**
     * 将原始的数组范围保存起来，用于恢复数组
     */
    private int r;

    private int c;

    /**
     * 洗牌的最大值范围
     */
    private int rightBoundary;

    public static void main(String[] args) {

        随机翻转矩阵_519 obj = new 随机翻转矩阵_519();
        obj.Solution(1, 3);
        System.out.println(Arrays.toString(obj.flip()));
        System.out.println(Arrays.toString(obj.flip()));
        System.out.println(Arrays.toString(obj.flip()));

    }

    /**
     * 洗牌算法
     * 虽然题目是二维数组，也可以将之看做一维数组
     * 有r行，c列
     * 0    1   2   ...   c-1
     * c    c+1 c+2 ...   2c-1
     * ...          ...   r*c-1
     * 假如
     * 有2行，3列
     * 0    1   2
     * 3    4   5
     * 3->[3/3,3%3]->[1,0]
     *
     * @param m
     * @param n
     */
    public void Solution(int m, int n) {
        r = m;
        c = n;
        //random.index(a,b)的随机取值范围是不包含右边界b的值
        rightBoundary = m * n;
    }

    public int[] flip() {
        Random random = new Random();
        int randomNum = random.nextInt(rightBoundary);
        //实际上-1之后才是数组可以取到的最大值，顺便将右边界缩减1
        rightBoundary--;
        //交换value，其实这里并不需要去维护无序的数组区间，只对前面的有序区间进行替换
        Integer realRandom = map.getOrDefault(randomNum, randomNum);
        if (randomNum != rightBoundary) {  //产生的随机数，正好是右边界，无序替换
            map.put(randomNum, map.getOrDefault(rightBoundary, rightBoundary));
        }
        return new int[]{realRandom / c, realRandom % c};
    }

    public void reset() {
        map.clear();
        rightBoundary = r * c;
    }

}
